package com.hanxiaozhang.no10leetcode.dynamicprogramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个可以看作是三角形的输入数组，找到从顶到底的最小路径，每一步只能移动到下一行相邻的元素上。
 * 例子：
 * [
 * [2],
 * [3,4],
 * [6,5,7],
 * [4,1,8,3]
 * ]
 * 从上到下的最小路径和为 11 (i.e., 2 + 3 + 5 + 1 = 11).
 * 注意：如果你只使用O(n)额外的空间就可以做到这一点，那么这将是一个加分项，其中n是三角形中的总行数。最好空间复杂度为O(n)
 *
 * @author hanxinghua
 * @create 2024/3/4
 * @since 1.0.0
 */
public class No120Triangle {

    public static void main(String[] args) {

        int[][] nums = {
                {2},
                {3, 4},
                {6, 5, 7},
                {4, 1, 8, 3}
        };

        int[][] nums1 = {
                {-1},
                {-2, -3}
        };

        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(new Integer[]{2}));
        triangle.add(Arrays.asList(new Integer[]{3, 4}));
        triangle.add(Arrays.asList(new Integer[]{6, 5, 7}));
        triangle.add(Arrays.asList(new Integer[]{4, 1, 8, 3}));

        List<List<Integer>> triangle1 = new ArrayList<>();
        triangle1.add(Arrays.asList(new Integer[]{-1}));
        triangle1.add(Arrays.asList(new Integer[]{-2, -3}));


        System.out.println(method1(triangle1));

//        List<Integer> results = new ArrayList<>();
//        Integer temp = nums[0][0], lastIndex = 0;
//
//        // 行
//        for (int i = 1; i < nums.length; i++) {
//            // 列
//            for (int j = 0; j < nums[i].length; j++) {
//
//
//            }
//        }
    }


    /**
     * 方法1
     *
     * @param triangle
     * @return
     */
    private static int method1(List<List<Integer>> triangle) {
        List<Integer> results = new ArrayList<>();
        Integer result = triangle.get(0).get(0);

        backTrack(results, result, triangle, 1, 0);

        int min = Integer.MAX_VALUE;
        for (Integer x : results) {
            min = Math.min(x, min);
        }
        return min;
    }

    private static void backTrack(List<Integer> results, Integer result, List<List<Integer>> triangle, int index, int start) {

        if (index == triangle.size()) {
            results.add(result);
            return;
        }
        for (int i = start; i <= start + 1; i++) {
            result += triangle.get(index).get(i);
            backTrack(results, result, triangle, index + 1, i);
            result -= triangle.get(index).get(i);
        }
    }


    public static int method2(List<List<Integer>> triangle) {
        if (triangle == null) {
            return 0;
        }
        int length = triangle.size();
        int[] sums = new int[length];
        sums[0] = triangle.get(0).get(0);
        //  行
        for (int i = 1; i < length; i++) {
            List<Integer> list = triangle.get(i);
            sums[i] = sums[i - 1] + list.get(i);
            // 贪心，找当前步骤最小 todo
            for (int j = i - 1; j > 0; j--) {
                sums[j] = Math.min(sums[j - 1], sums[j]) + list.get(j);
            }
            sums[0] += list.get(0);
        }

        int min = Integer.MAX_VALUE;
        for (int i : sums) {
            min = Math.min(min, i);
        }
        return min;
    }
}
